package leetcode;

import java.util.Scanner;

public class 数列求值递归与递推 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int  x=di(n);
        System.out.println(x);
    }
//    public static long   di(int n){//处理不了大数据
//        if(n==1||n==2||n==3)return 1;
//        else {return (di(n-1)+di(n-2)+di(n-3))%10000;}
//    }
    public static int di(int n){//递推时间复杂度On

        int a=1;
        int b=1;
        int c=1;
        int d=0;
        if(n<=3)return 1;
        else{
            for (int i = 4; i <=n; i++) {
               d=(a+b+c)%10000;
               a=b;
               b=c;
               c=d;

            }
            return d;
        }
    }

}
